#!/usr/bin/python
# -*- coding: UTF-8 -*-

from math import *
import queue
import sys
import time
import os
from datetime import datetime
import pymssql
import pandas as pd
import numpy as np
import datetime
import math
sys.path.append(r'C:\Users\Administrator\Desktop')
from CarRecord import *
from Arc import *
from ArcMany import *
from CarPath import *

#通过经纬度计算两点之间的距离
def DistanceBetween(geo1, geo2):
    return pow(pow(float(geo1[0]) - float(geo2[0]), 2) + pow(float(geo1[1]) - float(geo2[1]), 2), 0.5)

# 知道三个顶点坐标ABC，看角ACB是否是锐角三角形
def CheckOxygon(A, C, B):
    a = DistanceBetween(C, B)
    b = DistanceBetween(A, C)
    c = DistanceBetween(A, B)
    if a ** 2 + b ** 2 < c ** 2:
        return False
    else:
        return True

# 计算起点到终点线段方向与y轴的夹角 逆时针
# geo_list 第一个参数-1终点 0起点 第二个参数 0纬度 1经度
def CalDirection(geo_list):
    if geo_list[-1][0] == geo_list[0][0]:
        if geo_list[-1][1] > geo_list[0][1]:
            return float(0)
        else:
            return float(180)
    else:
        # tan=slope
        # arctan(tan x)=x
        slope = (geo_list[-1][1] - geo_list[0][1]) / (geo_list[-1][0] - geo_list[0][0])
        if geo_list[-1][0] >  geo_list[0][0]: # 如果射线在第1,2象限
            return 90 - (atan(slope) / pi * 180) # 由于角度是跟y轴的夹角，所以需要90-
        else: # 如果射线在第3,4象限
            return 90 - (atan(slope) / pi * 180) + 180

# 传入geo1, geo2为直线y = kx + d上两点，求geo3在直线上的射影（即作垂直后与直线的交点）
# 如果形成钝角三角形，则垂点取geo1，geo2中靠近geo3的那个  就是直接过去
def CalProjection(geo1, geo2, geo3):
    geo1 = [float(ele) for ele in geo1]
    geo2 = [float(ele) for ele in geo2]
    geo3 = [float(ele) for ele in geo3]
    a = DistanceBetween(geo2, geo3)
    b = DistanceBetween(geo1, geo3)
    c = DistanceBetween(geo1, geo2)
    if (a**2 + c**2) <= b**2: #钝角三角形，且geo3靠近geo2，包括点在线段延长线上的情况
        return geo2
    elif b**2 + c**2 <= a**2: #钝角三角形，且geo3靠近geo1，包括点在线段延长线上的情况
        return geo1
    elif a + b == c: # 说明点在线段上
        return geo3
    else:
        if geo1[0] == geo2[0]: # 如果直线竖直
            return [geo1[0], geo3[1]]
        elif geo1[1] == geo2[1]: # 如果直线水平
            return [geo3[0], geo1[1]]
        else:
            k = (geo1[1] - geo2[1]) / (geo1[0] - geo2[0]) # y = kx+d中的k
            d = geo1[1] - k * geo1[0] # y = kx+d中的d
            x4 = (k * geo3[1] - k * d + geo3[0]) / (1 + k**2) #先求交点经度
            y4 = k * x4 + d #再求交点纬度
            return [x4, y4]


#逐个计算路段的点、与路段延长点、出租车点的的夹角
def CalProjectionOfArc(arc, geo):
    length = len(arc.geometry_list)
    # 先找一个虚拟点，其为点arc.geometry_list[-2]到arc.geometry_list[-1]连线延长线上延长相等距离的点
    virtual_p = [(2 * arc.geometry_list[-1][i] - arc.geometry_list[-2][i]) for i in range(2)]
    # 找从哪个i开始，三角形ACB变成钝角，其中点A为car_record.geo,点C为arc.geometry_list[i]，点B为virtual_p
    i = 0
    while i < length - 1 and CheckOxygon(geo, arc.geometry_list[i], virtual_p):  # 判断是否是锐角
        i += 1
    # 如果最小的i为0或者len() - 1，则取最靠近目标点的两个点计算垂点
    # 即使第一个点就出现钝角三角形的情况，calProjection函数中会处理
    if i == 0:  # 如果垂点在线段上
        projection = CalProjection(arc.geometry_list[i], arc.geometry_list[i + 1], geo)
    else:  # 如果垂点在线段上
        projection = CalProjection(arc.geometry_list[i - 1], arc.geometry_list[i], geo)
    return projection


# 传入geo1, geo2为直线y = kx + d上两点，求geo3到直线的距离
# 如果形成钝角三角形，则垂点取geo1，geo2中靠近geo3的那个点与geo3的距离
def CalDistance(geo1, geo2, geo3):
    geo1 = [float(ele) for ele in geo1]
    geo2 = [float(ele) for ele in geo2]
    geo3 = [float(ele) for ele in geo3]
    a = DistanceBetween(geo2, geo3)
    b = DistanceBetween(geo1, geo3)
    c = DistanceBetween(geo1, geo2)
    if (a ** 2 + c ** 2) <= b ** 2:  # 钝角三角形，且geo3靠近geo2，包括点在线段延长线上的情况
        return DistanceBetween(geo2, geo3) * 5  # *5是geo点跑到外面去的panelty
    elif b ** 2 + c ** 2 <= a ** 2:  # 钝角三角形，且geo3靠近geo1，包括点在线段延长线上的情况
        return DistanceBetween(geo1, geo3) * 5
    elif a + b == c:  # 说明点在线段上
        return 0
    else:
        if geo1[0] == geo2[0]:  # 如果直线竖直
            return abs(geo3[0] - geo1[0])
        elif geo1[1] == geo2[1]:  # 如果直线水平
            return abs(geo3[1] - geo1[1])
        else:
            k = (geo1[1] - geo2[1]) / (geo1[0] - geo2[0])  # y = kx+d中的k
            d = geo1[1] - k * geo1[0]  # y = kx+d中的d
            dist = abs(k * geo3[0] + d - geo3[1]) / sqrt(1 + k ** 2)  # 点到直线距离公式
            return dist

# 如果汽车定位数据跟道路的相差很远或者方向不对，则没有必要取该条arc
def CheckNecessary(arc, car_record):
    # 如果edgh方向和汽车的方向不同，则认为车不在该道路上
    # 速度小于3m/s的汽车定位点方向不可信，因此不判断其与路段的方向。/LOU
    if car_record.speed > 3 * 3.6:
        diff_angle = abs(car_record.direction - arc.direction)
        if diff_angle > 180:
            diff_angle = 360 - diff_angle
        if diff_angle > 90:  # 如果道路方向和汽车方向不同
            return False
    # 我计算了该地图中最长的路，取一半的大一点，即1000，防止出现漏判的情况，因为下面这个if是只取每段道路的坐标的起点和终点来跟目标点计算距离
    if DistanceActual(arc.geometry_list[0], car_record.geo) > 1000:
        if DistanceActual(arc.geometry_list[-1], car_record.geo) > 1000:
            return False
    # 下面if是计算这条道路上有一gps点跟目标点的最短距离小于100m才返回True。我们认为汽车gps精度为20m，放宽到100m
    min_dist = float("inf")
    for geo1 in arc.geometry_list:
        tmp = DistanceActual(geo1, car_record.geo)
        if tmp < min_dist:
            min_dist = tmp
    if min_dist < 100:
        return True
    else:
        return False

# 计算GPS匹配到该路段的成本系数cost
def CalCost(arc, car_record):
    cost = float("inf")
    # CheckNecessary函数首先排除与车辆定位点距离相差远、方向不匹配的路段。/LOU
    if CheckNecessary(arc, car_record):
        # arc.geometry_list为路段gps点集合，length记录gps点个数。/LOU
        length = len(arc.geometry_list)
        # 先找一个虚拟点，其为点arc.geometry_list[-2]到arc.geometry_list[-1]连线延长线上延长相等距离的点
        # 虚拟点virtual_p在道路最后一个gps点之后。/LOU
        virtual_p = [(2 * arc.geometry_list[-1][i] - arc.geometry_list[-2][i]) for i in range(2)]
        # 找从哪个i开始，三角形ACB变成钝角，其中点A为car_record.geo,点C为arc.geometry_list[i]，点B为virtual_p
        i = 0
        # CheckOxygon检查车辆与道路第i点的连线，与道路的夹角是否为锐角，是锐角继续循环。/LOU
        while i < length - 1 and CheckOxygon(car_record.geo, arc.geometry_list[i], virtual_p):
            i += 1
        # 如果最小的i为0或者len() - 1，则取最靠近目标点的两个点计算垂点
        # 即使出现钝角三角形的情况，calProjection函数中会处理
        if i == 0:
            # dist为车辆定位点与道路的距离，direction_road为道路方向，作为之后计算cost的直接、间接的参数。/LOU
            dist = CalDistance(arc.geometry_list[i], arc.geometry_list[i + 1], car_record.geo)

            direction_road = arc.direction
        else:  # 如果垂点在线段上
            dist = CalDistance(arc.geometry_list[i - 1], arc.geometry_list[i], car_record.geo)
            direction_road = CalDirection(arc.geometry_list[i - 1: i + 1])
        # 综合考虑汽车与道路方向差、距离，得出车辆定位点与路段匹配的cost。/LOU
        diff_angle = abs(car_record.direction - direction_road)
        if diff_angle > 180:
            diff_angle = 360 - diff_angle
        # 车速越大，可信度更高，方向所占比重越大。/LOU
        if car_record.speed < 1 * 3.6:  # 如果车速小于1，方向所占比重为0
            angle_ratio = 0
        elif car_record.speed < 10 * 3.6:  # 如果车速在1m/s到10m/s之间，随着车速增加，方向所占比重逐渐增加到0.54
            angle_ratio = (car_record.speed / 3.6 - 1) * 0.06
        else:  # 如果速度大于10m/s，方向所占比重保持0.54不变
            angle_ratio = 0.54
        # 从提供的道路数据的第1条可以知道经纬度的0.00046对应实际距离39.3m。/LOU
        cost = (dist*111000) * (1 - angle_ratio) + (1.5 * diff_angle) * angle_ratio
    return cost

# 给定car_geo和car_direction，根据最短距离和方向，计算在所有道路的Cost，返回Cost最小的道路id
def CalMinCostArcID(car_record):
    min_cost = float("inf")
    id = 0
    # arc_objects存储着所有边的Arc对象实例，即所有路段信息。/LOU
    for arc in arc_objects:
        cost = CalCost(arc, car_record)
        if cost < min_cost:
            min_cost = cost
            id = arc.id
    return id

# 计算时长
def SecondsBetween(t1, t2):
    big = datetime.datetime.strptime(str(t2), "%Y-%m-%d %H:%M:%S")
    small = datetime.datetime.strptime(str(t1), "%Y-%m-%d %H:%M:%S")
    return (big - small).total_seconds()

# 返回两个gps点的实际距离，经纬度与米的换算约为1:111000。/LOU
def DistanceActual(geo1, geo2):
    return pow(pow(float(geo1[0]) - float(geo2[0]), 2) + pow(float(geo1[1]) - float(geo2[1]), 2), 0.5)*111000

# 输入arc_cover是arc_id和cover的列表，该函数输出这个arc_cover包含的道路总长
def CalLenCover(arc_cover):
    travel_distance = 0
    for k in range(len(arc_cover)):
        travel_distance += arc_objects[arc_cover[k][0] - 1].len * arc_cover[k][1]
    return round(travel_distance,1)

# 输入arc_list是arc_id的列表，该函数输出这个arc_list包含的道路总长
def CalLen(arc_list):
    travel_distance = 0
    for k in range(len(arc_list)):
        travel_distance += arc_objects[arc_list[k] - 1].len
    return round(travel_distance,1)

# 拿着我的集合找最短的
def findMinDist(dist, collected):
    min_dist = float("inf")
    min_key = -1
    for key in dist:
        if dist[key] < min_dist and (key not in collected.keys()):
            min_dist = dist[key]
            min_key = key
    return min_key

# 用单源最短路径算法，求两条边的最短距离的arc_list
# graph：邻近路网关系图；start_arc_id：起点路段；end_arc_id：终点路段
def dijkstra(graph, start_arc_id, end_arc_id):
    if start_arc_id == end_arc_id:  # 当前一路段与后匹配路段一样
        return [start_arc_id]
    dist = {}
    path = {}
    collected = {}
    # 初始化距离为无穷大
    for key in graph:
        dist[key] = float("inf")
        for arc in graph[key]:
            if not arc.to_node in dist.keys():  # 如果邻近路网关系图中没有路段的起点等于arc的终点
                dist[arc.to_node] = float("inf")
    from_node = arc_objects[start_arc_id - 1].to_node  # 起始路段起点
    to_node = arc_objects[end_arc_id - 1].from_node  # 终止路段终点
    if from_node in graph.keys():  # 如果graph中有路段起点与from_node一致
        for arc in graph[from_node]:  # 遍历路段起点与from_node一致的路段
            dist[arc.to_node] = arc.len  # 更新始路段起点到该点的距离
            path[arc.to_node] = from_node  # 更新始路段起点到该点的路径
    dist[from_node] = 0  # 起始路段起点到起始路段起点距离为0
    collected[from_node] = True
    while True:
        node = findMinDist(dist, collected)
        if node == -1:
            break
        collected[node] = True
        if node in graph.keys():
            for arc in graph[node]:
                if arc.to_node not in collected.keys():
                    if dist[arc.to_node] > dist[node] + arc.len:
                        dist[arc.to_node] = dist[node] + arc.len
                        path[arc.to_node] = node
    arc_list = [end_arc_id]# 先放入终点
    while to_node in path.keys():
        for arc in graph[path[to_node]]:
            if arc.to_node == to_node:
                arc_list.append(arc.id)
        to_node = path[to_node]
    arc_list.append(start_arc_id) #最后放入起点
    arc_list = arc_list[::-1] #两级反转
    return arc_list

#arc：上一个GPS点所匹配的路径，car_record：GPS点对象，dist：arc终点到GPS点的距离
def BFSFindPathArc(arc, car_record, dist):
    min_cost = 60  # min_cost初始值为60近似为无限大
    arc_list = []  # arc_list是GPS点从上一个点走过的路径集合
    min_arc_id = 0  # min_arc_id是得到最小cost的路段
    visited = {}  # visited 里面记录着已经搜索过计算过cost的路段
    graph_around = {}  # graph_around是连接着上一匹配路段的临近路段集合。
    q = queue.Queue()  # q是一个队列，里面存放需要计算cost的备选路段
    q.put(arc)  # 将arc放入队列
    visited[arc.id] = True  # 表示arc已经搜索过
    while not q.empty():  # 当q里还有需要计算cost的路段，则继续循环
        arc1 = q.get()  # 将q里最后放进去的路段拿出并从q里删除
        # 生成arc附近连通的道路的图，后面用来找最短路径
        if arc1.from_node in graph_around.keys():
            graph_around[arc1.from_node].append(arc1)  # 将起点ID相同的路段放入同一个索引
        else:
            graph_around[arc1.from_node] = [arc1]
        cost = CalCost(arc1, car_record)  # 计算arc1的cost
        if cost < min_cost:
            min_cost = cost  # 更新最小cost
            min_arc_id = arc1.id   # 更新最小cost的路段
        if arc1.to_node in map_graph.keys():  # 如果arc1路段的终点在地图临近关系表map_graph里
            for arc2 in map_graph[arc1.to_node]:  # 在以arc1路段终点为起点的路段集合里做循环，以arc2变量表示
                if arc2.id not in visited.keys():  # 如果arc2不在visited集合中
                    if DistanceBetween(arc.geometry_list[-1], arc2.geometry_list[0]) < dist*1.5:
                        # 如果arc1终点到arc2的起点的距离 小于 arc终点到GPS点的距离
                        q.put(arc2)  # 将arc2放进队列
                        visited[arc2.id] = True  # 将arc2标记已搜索
    if min_arc_id != 0:
        arc_list = dijkstra(graph_around, arc.id, min_arc_id)   # 计算前一匹配路段到现匹配路段的最短路径
    return arc_list

# 计算car_i经过的路径，将路段index记录在car_i_start_end_inde_list中，路径以j表示 /LOU
def CarRecordsDivide(car_i):
    # car_id_count存储着从1到100每一条OD的gps定位数量 /LOU
    index_start = sum(car_id_count[:car_i-1])  # 第i条OD数据的起始索引位置
    index_end = sum(car_id_count[:car_i])  # 第i条OD数据的终止索引位置
    car_i_start_end_index_list = []
    car_i_start_end_index_list.append([index_start, index_end])
    return car_i_start_end_index_list

#计算属于一天中的第几个小时
def Time_stage(gps_time):
    today_time=datetime.datetime(2019, 2, 18, 0, 0, 0)
    return math.ceil(SecondsBetween(today_time, gps_time)/3600)


# #####################################################导入数据########################################################################

###从SQLsever导入出租车GPS数据
conn = pymssql.connect(host='MachineOfWayson',user='',password='',database='DATA')  # 输入主机名，数据库用户名，数据库密码，与ODBC连接的、所用的数据库。
cur = conn.cursor()
cur.execute("SELECT  * FROM [DATA].[dbo].[taxi] where [OD序列号] <100  order by [OD序列号],[GPS_TIME] ")
#如果是插入、删除、更新语句切记要写提交命令con.commit()
Gps_data2 = cur.fetchall()  #数据库读取的数据放到Gps_data2中
cur.close()
conn.close()
car_record_objects = [CarRecord(line_str) for line_str in Gps_data2]  # 将Gps_data2的数据逐行读取并使用CarRecord创建对象
print("出租车数据量："+str(len(car_record_objects)))
car_id = [car_record.car_id for car_record in car_record_objects]  # 提取数据中的car_id列，如[1,1,1,2,2,2]
car_num = max(car_id)
car_id_count = [car_id.count(i + 1) for i in range(car_num)]  # 计算每条OD的GPS数据量，如[32,46,33]


###从SQLsever导入地图数据
conn=pymssql.connect(host='WIN-KU0G987DS16',user='',password='',database='QQ')
cur1=conn.cursor()
cur1.execute("SELECT * FROM [DATA].[dbo].[python路网0] order by 路段ID")
#如果是插入、删除、更新语句切记要写提交命令con.commit()
Arc_data2 = cur1.fetchall()
cur1.close()
conn.close()
arc_objects = [Arc(line_str) for line_str in Arc_data2]


###将地图的节点改为间距20米的密集节点
conn = pymssql.connect(host='WIN-KU0G987DS16',user='',password='',database='QQ')
cur = conn.cursor()
sql = "select [列 0],[列 1],[路段ID] from [DATA].[dbo].[道路密集分布点] order by 路段ID,序号"
cur.execute(sql)
Arc_many = cur.fetchall()
cur.close()
conn.close()
Arc_many_objects = [ArcMany(line_str) for line_str in Arc_many]
Arc_many_id = [Arc_many.id for Arc_many in Arc_many_objects]  # Arc_many_objects的id合集
Arc_many_num = max(Arc_many_id)
Arc_many_count = [Arc_many_id.count(i + 1) for i in range(Arc_many_num)]  # Arc_many_objects每条路的密集点的数量
# 得到id为i的路段的密集点集合
def ArcmanyRecordsDivide(Arcmany_i):
    Arcmany_index_start = sum(Arc_many_count[:Arcmany_i])  #第i路段的起始索引位置
    Arcmany_index_end = sum(Arc_many_count[:Arcmany_i + 1])  #第i路段的终止索引位置
    Arcmany_record_list = Arc_many_objects[Arcmany_index_start: Arcmany_index_end]  # 每个路段的点集合
    Arcmany_geo_list = [Arcmany_record.geometry_list2 for Arcmany_record in Arcmany_record_list]  # 每个路段的点的经纬度集合
    return Arcmany_geo_list
#arc_objects里的路段经纬度更新为点集合
for i in range(0, len(Arc_data2)):  # 对每条路段循环
    del arc_objects[i].geometry_list[0:4]  # 删除第i条路段原有的经纬度信息
    Arcmany_record_list_i=ArcmanyRecordsDivide(i)  # 提取第i条路段新的密集点经纬度信息
    for j in range(0, len(Arcmany_record_list_i)):  # 对第i条路段新的密集点经纬度信息循环
        arc_objects[i].geometry_list.append(Arcmany_record_list_i[j])  # 在第i条路段经纬度列加上 新的密集点经纬度第j条信息


# 生成图的邻接表数据结构
# map_graph的每个索引里面对应着有相同起点的路段。比如，对应所有i，map_graph[1][i].from_node的值相同，i是与节点id为1相连的所有其他节点。
map_graph = {}
for arc in arc_objects:
    if arc.from_node in map_graph.keys():  # 判断map_graph的第arc.from_node列是否存在有数据
        map_graph[arc_objects[arc.id - 1].from_node].append(arc)  # 有值，则附加一个数据
    else:
        map_graph[arc_objects[arc.id - 1].from_node] = [arc]  # 没有，则放入数据

def main():
    arc_path = []  # 存放总匹配数据
    for car_i in range(1, car_num+1):   # 对OD进行循环
        car_i_start_end_index_list = CarRecordsDivide(car_i)
        print("\n\n第" + str(car_i) + "条OD,索引为："+str(car_i_start_end_index_list))
        car_ij_start_index = car_i_start_end_index_list[0][0]  # 第i段OD数据的第一个定位数据
        car_ij_end_index = car_i_start_end_index_list[0][1]  # 第i段OD数据的第最后一个定位数据，不包括该条记录
        # 对于刚起步的20米范围内的点，合并为一个点计算。因为前面的点车头方向不稳定不好判断
        j = car_ij_start_index
        while j < car_ij_end_index:
            if DistanceActual(car_record_objects[j].geo, car_record_objects[car_ij_start_index].geo) > 20:
                break
            j += 1
        # 将前第i辆车的第j段轨迹20m内的定位点存入car_record_list。/LOU
        car_record_list = car_record_objects[car_ij_start_index: j]  # 轨迹集合
        car_geo_list = [car_record.geo for car_record in car_record_list]  # 经纬度集合
        car_x = sum([geo[0] for geo in car_geo_list]) / len(car_geo_list)  # 取平均经度
        car_y = sum([geo[1] for geo in car_geo_list]) / len(car_geo_list)  # 取平均纬度
        car_direction = car_record_list[-1].direction  # 将20m内的定位点的最后一个点的方向作为平均方向
        car_20_id = car_record_list[-1].car_id
        car_20 = car_record_list[-1].car
        id_20 = car_record_list[-1].id
        car_20_time = car_record_list[-1].time
        car_record = CarRecord([car_20, car_20_time, car_x, car_y, 0, 36, car_direction, 0, id_20, 0, car_20_id])  # 合并后的点的对象
        path_tem = CarPath([CalMinCostArcID(car_record), car_record.id, Time_stage(car_record.time)])
        print('path_tem ' + str(path_tem.path) + ',' + str(path_tem.id) + ',' + str(path_tem.time_stage))
        arc_path.append(path_tem)
        # print('arc_path'+str(arc_path))
        while j < car_ij_end_index:
            # car_record_objects是除初始点之外的汽车GPS定位点，依次匹配，循环结束后汽车i的第j段轨迹所有定位点均匹配到路网上。/LOU
            car_record = car_record_objects[j]  # 取下一个点
            arc_list2 = BFSFindPathArc(arc_objects[arc_path[-1].path - 1], car_record,
                                       DistanceBetween(car_record.geo,
                                                       arc_objects[arc_path[-1].path - 1].geometry_list[-1]))
            arc_list = arc_list2.copy()
            path_tem = []
            for i in range(0, len(arc_list)):  # 对每条路段循环
                path_tem.append(CarPath([arc_list[i], car_record.id, Time_stage(car_record.time)]))
            if len(arc_list) != 0:
                arc_path = arc_path + path_tem
            else:  # 如果路径匹配失败
                print("非1")
                if len(arc_path) > 1:  # 如果arc_path有两条或以上数据，则利用倒数第二条数据进行轨迹匹配
                    arc_list = BFSFindPathArc(arc_objects[arc_path[-2].path - 1], car_record,
                                              DistanceBetween(car_record.geo,
                                                              arc_objects[arc_path[-2].path - 1].geometry_list[-1]))
                    path_tem = []
                    for i in range(0, len(arc_list)):  # 对每条路段循环
                        path_tem.append(CarPath([arc_list[i], car_record.id, Time_stage(car_record.time)]))
                    if len(arc_list) != 0:
                        arc_path = arc_path + path_tem
                    else:
                        if len(arc_path) > 2:  # 如果arc_path有两条或以上数据，则利用倒数第三条数据进行轨迹匹配
                            arc_list = BFSFindPathArc(arc_objects[arc_path[-3].path - 1], car_record,
                                                      DistanceBetween(car_record.geo,
                                                                      arc_objects[arc_path[-3].path - 1].geometry_list[
                                                                          -1]))
                            path_tem = []
                            for i in range(0, len(arc_list)):  # 对每条路段循环
                                path_tem.append(CarPath([arc_list[i], car_record.id, Time_stage(car_record.time)]))
                            if len(arc_list) != 0:
                                arc_path = arc_path + path_tem
                        else:
                            j = car_ij_end_index
                else:  # 如果arc_path只有1条数据，则直接用最小成本匹配出一条道路
                    # arc_id = CalMinCostArcID(car_record)
                    # if arc_id != 0:
                    #     path_tem.append(CarPath([arc_id, car_record.id, Time_stage(car_record.time)]))
                    #     arc_path.append(arc_id)
                    j = car_ij_end_index
            j += 1
        for i in range(0, len(arc_path)):
            print("\n第" + str(car_i) + "段OD第" + str(arc_path[i].id) + "点经过的路段ID：" + str(arc_path[i].path))


    # 将运行结果导出数据库
    link_output = []
    for i in range(0, len(arc_path)):
        link_output.append((arc_path[i].path, arc_path[i].id, arc_path[i].time_stage,i))
    print(link_output)
    conn2 = pymssql.connect(host='WIN-KU0G987DS16', user='', password='', database='DATA')
    cursor = conn2.cursor()
    #sql2 = "drop table output"
    #cursor.execute(sql2)
    sql3 = "create table [DATA].[dbo].output(path int, id int ,time_stage int, index_id int)"
    cursor.execute(sql3)
    sql_path = "INSERT INTO [DATA].[dbo].output VALUES ('%d','%d','%d','%d')"
    # 格式符为真实值预留位置,%s：子符串 (采用str()的显示)。%d：十进制整数
    cursor.executemany(sql_path, link_output)
    conn2.commit()
    print('写入数据库成功')
    cursor.close()
    conn2.close()  # 关闭数据库

if __name__ == '__main__':
    start = time.clock()
    main()
    end = time.clock()
